A backward chaining system begins with a goal and tries to prove that goal by ascertaining facts that can establish it. In trying to determine the goal, it examines all queries and rules that could assert the goal in question until it either reaches a conclusion or exhausts the rules. The order of the rules in the rule base and, within the rules, the order of the facts determines the search order.
The logic for backward chaining can be expressed as follows:
main:
get goal (fact to be determined) from user
process fact(goal)
end main
process fact(fact)
if fact has a query then
prompt user and get answer
assert fact
else
set pointer to top of rule base
while rules remain and fact not asserted
get next rule
if rule can assert fact then
while clauses remain
if fact in clause asserted then
evaluate clause
else
process fact(unknown fact)
end if
end while
if rule proved true then
assert fact
process daemons(fact)
if rule draws conclusion
post conclusion
end if
end if
end if
end while
end if
end process fact
Note that the call to "process fact" within the routine "process fact" is a recursive call and that it passes in the unknown fact. Thus, when a backward chaining system encounters an unknown fact while evaluating a rule, it will attempt to assert that fact. Typically, the fact that is the goal of the system will not have a query associated with it but will have multiple rules capable of asserting the fact (goal).
We will now walk through a session with our sample rule base. In our sample, fact "model" is the goal. The system will evaluate each of the rules capable setting fact "model" (our goal) until either one asserts fact "model" or it exhausts the possibilities.
You may walk through this example using the shell. Go to the "tutorial shell" card. Click on the "load RB" button to make certain that the rule base is loaded in the "Rule Base" field. Next if the "Forward Chain/Backward Chain" field does not show "Backward Chain", click on it to toggle it to "Backward Chain".
If you would like to monitor the process, click on the "trace" check box to set trace on (an X will show in the box when it is on). To step through the process, click on the "step" check box to set step on (an X will show in the box when it is on).
Next, click on the "(re)start" button to start the session and answer the questions or follow the directions as they appear in the "Query" field. You should enter "model" in response to the "Enter goal..." query. During the session you may toggle between this card and others in the stack. The shell will retain its state when you toggle among cards; you do not have to start over each time that you return to the shell.
If you checked both trace and step, watch the "Trace" field to see the actions taken by the system. The system will show the state of the stack in the "Stack" field and the facts and their values in the "Facts" field.
NOTE: The system handles daemons and traces actions with respect to them. You will notice that whenever a fact is asserted, that fact is pushed on the stack while the system looks for daemons associated with it. Therefore, the fact name will appear twice on the stack during that processing. For this tutorial, ignore these actions taken by the system concerning daemons.
The system begins by pushing the goal "model" on the stack. It then searches for queries or rules which can establish that goal, or fact. It first finds rule "Corvette", pushes that rule on the stack, and attempts to evaluate it. Since the first clause, "rule car", requires fact "car" which has not been asserted, the system pushes fact "car" on the stack.
The system then searches for a query or rule asserting fact "car". It finds rule "car 1" and pushes it on the stack. In evaluating rule "car 1" the system finds that fact "wheels" has not been asserted and pushes it on the stack.
Fact wheels has a query associated with it, so the system asks "How many wheels does it have?". Answer "4". The system asserts fact "wheels = 4", processes daemons, and pops fact "wheels" from the stack.
The system resumes evaluation of rule "car 1" and is now able to evaluate the clause concerning "wheels". However, it finds that fact "passengers" has not been asserted, so it pushes fact "passengers" on the stack.
Fact "passengers" has a query associated with it, so the system asks "How many passengers can it carry?". Answer "4". The system asserts fact "passengers = 4", processes daemons, and pops fact "passengers" from the stack.
The system then continues evaluating rule "car 1" and completes the clause concerning "passengers". However, it finds that fact "used for cargo" has not been asserted, so it pushes fact "used for cargo" on the stack.
Fact "used for cargo" has a query associated with it, so the system asks "Is it used to carry cargo?". Answer "no". The system asserts fact "used for cargo = no", processes daemons, and pops fact "used for cargo" from the stack.
Now the system is able to complete evaluation of rule "car 1". It finds the rule true and executes the "then" part of the rule, asserting fact "car = true", processing daemons, and popping rule "car 1" from the stack. Since fact "car" has been asserted, it is also popped from the stack.
The system resumes evaluation of rule "Corvette" and finds that fact "make" has not been asserted, so it pushes fact "make" on the stack.
Fact "make" has a query associated with it, so the system asks "What is the make of the vehicle?". Answer "Chevy". The system asserts fact "make = Chevy", processes daemons, and pops fact "make" from the stack.
The system continues evaluating rule "Corvette" finding the clause concerning
"make" true. However, it finds that fact "passengers" does not match the clause. Therefore, the rule "Corvette" proves false and, since there is no ELSE clause, it is popped from the stack.
The system now searches for the next rule capable of asserting "model", finds rule "Camaro" and pushes it on the stack. It evaluates rule "Camaro", finds that it proves true, and executes the "then" part of the rule. From the "then" part of the rule, the system asserts the fact "model = Camaro", processes daemons, and displays the conclusion "The car is a Camaro". Since rule "Camaro" is finished, the system pops it from the stack. Since fact "model" has been resolved, the system pops it from the stack.
If the user chooses to continue, the system will not continue the search because the stack is empty.
After walking through the tutorial for this case, add a query for the fact "car" and watch the response. Add the query to the fact declaration section as shown.
fact
car
"the vehicle is a car, true or false?",
passengers
"How many passengers can it carry?",
wheels
"How many wheels does it have",
"used for cargo"
"Is it used to carry cargo?",
make
"What is the make of the vehicle?"
The query for fact "car" will wrap in the "Rule Base" field on the "tutorial shell" card. You should let it wrap. DO NOT place a carriage return inside of the quotes.
Now click on "(re)start" and begin the session (do not click on "load RB" or it will restore the rule base to its original condition). During the consultation, you will see that the system will ask "the vehicle is a car, true or false?" when trying to determine the fact "car". If you answer the question (answer "true" or "false"), it will not ask about facts "wheels" and "used for cargo". It will, however, ask about "passengers" when that fact is needed for other rules. If you enter only a carriage return (indicating that you do not know the answer), it will ask about facts "wheels" and "used for cargo" in order to determine fact "car".
Now let's force the system to examine all rules when attempting to find "model". To do that we must change the "put-into" statement for the rules "Corvette",
"Camaro", and "Mustang" to set fact "model" to the null string as shown (click on "load RB" first to restore the original rule base).
rule Corvette
if
fact car and
fact make = Chevy and
fact passengers = 2
then
put "" into fact model
conclude "The car is a Corvette."
rule Camaro
if
fact car and
fact make = Chevy and
fact passengers = 4
then
put "" into fact model
conclude "The car is a Camaro."
rule Mustang
if
fact car and
fact make = Ford
then
put "" into fact model
conclude "The car is a Mustang."
Now, run the system (don't forget to "(re)start" and answer as indicated in the detailed example above. You will notice that if you continue after it has found the model to be a Camaro, that it will examine the rule "Mustang". This is because the system considers a fact containing null ("") not asserted, so it will continue trying to assert that fact.
Try it again, only answer "*" when asked about the number of passengers. This will cause fact "passengers" to match anything and you will find that it will conclude that the car could be a Corvette or a Camaro.
Feel free to modify the rule base on the "tutorial shell" card and experiment with backward chaining. If you wish to restore the original sample rule base, simply click on the "load RB" button.
